package name.huzhenbo.java.algorithm.calculation;

class ClosestSub {
    private int[] input;
    private int targetSum;

    public ClosestSub(int[] input, int targetSum) {
        this.input = input;
        this.targetSum = targetSum;
    }

    public int recursiveGo() {
        if (input.length == 0) {
            return 0;
        }
        return _recursiveGo(0);
    }

    private int _recursiveGo(int start) {
        if (start == input.length - 1) {
            return input[start];
        }

        return minAbs(_recursiveGo(start + 1), toRightMin(start));
    }

    private int toRightMin(int start) {
        int min = input[start], minProceed = input[start];
        for (int i = start + 1; i < input.length; i++) {
            minProceed += input[i];
            min = minAbs(min, minProceed);
        }
        return min;
    }

    private int minAbs(int a, int b) {
        return absCompare(a, b) < 0 ? a : b;
    }

    private int absCompare(int a, int b) {
        return Math.abs(a - targetSum) - Math.abs(b - targetSum);
    }

}
